Test 2019.8.13 题解

2019-08-13

题目传送门

题解

T1 自数

题面较为简单，给出了一个概念：一个数可以产生一个由它本身加上各个位数上的数之和的数(有点拗口)，求l到r区间的所有不能被产生的数(相当于这个概念里的质数)。

解析：其实比较简单，数据也就1000000，可以定义一个 bool 数组，‘’1‘’代表该数是被产生的，’’0’’表示该数不能被产生，i 从 1 跑到 r,打一张表出来，最后从l 跑到 r，判断如果 !f[i]就输出。

#include<bits/stdc++.h>
#define re register int
#define L 100039
using namespace std;
int l,r,f[L],j,sum;
int main(){
    scanf("%d%d",&l,&r); //读入
    for(re i=1;i<=r+1;i++){
        int t=i;sum=t;  //sum用来记录每次产生数的值，t用来储存i的值
        while(t){sum+=t%10;t/=10;} //记录产生数的总和
        f[sum]=1;//还原
    }
    for(re i=l;i<=r;i++){
        if(!f[i])printf("%d\n",i); //输出
    }
    return 0;
}

T2 侦察守卫

非常简单的一道模拟题，因为数据范围十分小，所以可以直接暴力枚举

#include<bits/stdc++.h>
#define re register int
#define L 139
using namespace std;
int f[L][L],q,r;
struct FLY{int x,y,xx,yy;}s1,s2;
int main(){
    scanf("%d %d %d %d",&s1.x,&s1.y,&s1.xx,&s1.yy);
    scanf("%d %d %d %d",&s2.x,&s2.y,&s2.xx,&s2.yy);
    for(re i=s1.x;i<s1.xx;++i)
        for(re j=s1.y;j<s1.yy;++j)
            ++f[i][j];
    for(re i=s2.x;i<s2.xx;++i)
        for(re j=s2.y;j<s2.yy;++j)
            ++f[i][j];
    for(re i=1;i<=100;++i)
        for(re j=1;j<=100;++j)
            if(f[i][j]==1)++r;
            else if(f[i][j]==2)++q;
    printf("%d %d %d",q,r,10000-q-r);
    return 0;
}

T3 放牙刷

一道递推题，递推公式为f[i+1]=(f[i-1]+f[i])*i;

#include<bits/stdc++.h>
#define re register int
#defnie LL long long
using namespace std;
LL n,f[1000039];
int main(){
    scanf("%d",&n);
    if(n==1){printf("No Solution");return 0;}
    f[2]=1;f[3]=2;
    for(re i=3;i<=n;i++){
        f[i+1]=((f[i-1]+f[i])%1206)*(i%1206);
    }
    printf("%lld",f[n]%1206);
    return 0;
}

T4 安全逃离

也是一道模拟题，十分简单，先读入，之后把每个点拿走枚举一遍，如果可行，p++。最后一个特判：当p等于奶牛总数加一时输出‘’1‘’（因为每个奶牛撤走都行就代表这个地图是安全的），当p==1（初始化值）时输出‘’-1‘‘，最后输出奶牛编号

#include<bits/stdc++.h>
#define re register int
#define L 139
using namespace std;
int f[L][L],n,m,x[L],y[L],s,i,j,z,ans[L],k,p=1;
bool bx,by,b=1;
int scin(){
    scanf("%d%d",&n,&m),scanf("%d",&s);
    for(i=1;i<=s;i++){scanf("%d%d",&x[i],&y[i]);f[x[i]][y[i]]=1;}
}
int main(){
    scin();
    for(k=1;k<=s;k++){
        f[x[k]][y[k]]=0;
        for(z=1;z<=s;z++){
            if(z==k)continue;
            bx=0,by=0;
            for(i=x[z]-1;i>=1;i--)if(f[i][y[z]])bx=1;
            for(j=y[z]+1;j<=m;j++)if(f[x[z]][j])by=1;
            if(bx&&by)b=0;
        }
        if(b)ans[p++]=k;
        f[x[k]][y[k]]=1;b=1;
    }
    if(p==s+1)printf("0");
    else if(p>1)for(i=1;i<p;i++)printf("%d\n",ans[i]);
    else printf("-1");
    return 0;
}

-------------本文结束感谢您的阅读-------------

本文作者： jfy
本文链接： http://example.com/2019/08/13/Test%202019.8.13/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！